package linear_list.leetcode.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @author bruin_du
 * @description 复杂链表的复制
 * @date 2022/5/17 14:30
 **/
public class Offer35_CopyRandomList {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        //使用Map新的链表结点和原链表结点一一对应起来
        if (head == null)
            return null;
        //用Map存储原结点和新结点的一一对应关系
        Map<Node, Node> map = new HashMap<>();
        for (Node node = head; node != null; node = node.next) {
            map.put(node, new Node(node.val));
        }
        //根据原结点的关系通过键值对查到新结点的连接关系
        for (Node node = head; node != null; node = node.next) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
        }
        return map.get(head);

        //笨方法
        //将原链表的next和random保存下来,然后在两个链表中遍历找对应的结点连接
//        if(head == null)
//            return null;
//        Map<Node,Node> map = new HashMap<>();
//        Node pHead = head,newHead = null,pNewNode = null;
//        while(pHead != null){
//            Node node = new Node(pHead.val);
//            map.put(pHead.next,pHead.random);
//            if(newHead == null){
//                newHead = node;
//                pNewNode = node;
//            }else{
//                pNewNode = pNewNode.next = node;
//            }
//            pHead = pHead.next;
//        }
//        pHead = head;
//        pNewNode = newHead;
//        while(pHead != null){
//            Node randomNode = map.get(pHead.next);
//            if(randomNode == null){
//                pNewNode.random = null;
//            }else{
//                Node tmpNode = head;
//                Node tmpNewNode = newHead;
//                while(tmpNode != randomNode){
//                    tmpNode = tmpNode.next;
//                    tmpNewNode = tmpNewNode.next;
//                }
//                pNewNode.random = tmpNewNode;
//            }
//            pHead = pHead.next;
//            pNewNode = pNewNode.next;
//        }
//        return newHead;
    }
}
